<?php
class DoubleLinkedList {
	public $value;
	public $next;
	public $prev;
	
	public function __construct($v = null) {
		$this->value = $v;
		$this->next = null;
		$this->prev = null;
	}
	
	public function isEmpty() {
		return ($this->value == null);
	}
	
	public function hasNext() {
		return ($this->next != null);
	}
	
	public function hasPrev() {
		return ($this->prev != null);
	}	
	
}


abstract class PriorityList {
	/**
	 *
	 * @var DoubleLinkedList
	 */
	protected $first;	
	
	public function __construct() {
		$this->first = null;
	}
	
	public function isEmpty() {
		return ($this->first == null || $this->first->isEmpty());
	}	
	
	public function getAll() {
		$data=array();
		if ($this->isEmpty()) return;
		$current = $this->first;
		do {
			$data[] = $current->value;
		} while (($current = $current->next) != null);
	
		return $data;
	}	
	
}

class Queue extends PriorityList{

	
	/**
	 *
	 * @var DoubleLinkedList
	 */
	protected $last;	
	
	public function __construct() {
		$this->first = new DoubleLinkedList();
		$this->last = &$this->first;
	}
	
	
	public function enqueue($v) {
		if ($this->isEmpty()) {
			$this->first = new DoubleLinkedList($v);
			return;
		}
		
		$this->last->next = new DoubleLinkedList($v);
		$this->last = &$this->last->next;
		
	}
	
	public function dequeue() {
		$val = $this->first->value;
		$this->first = $this->first->next;
		return $val;
	}
	

}

class Stack extends PriorityList{
	
	public function push($v) {
		
		$newHead = new DoubleLinkedList($v);
		$newHead->next = $this->first;
		$this->first = &$newHead;
		
	}
	
	public function pop() {
		if ($this->isEmpty()) return null;
		$val = $this->first->value;
		$this->first = $this->first->next;
		return $val;
	}
	
	public function top() {
		if ($this->isEmpty()) return null;
		return  $this->first->value;		
	}
}